The present invention relates to implementation of encoding and decoding image data.
A number line encoding method (arithmetic encoding method) is also known as encoding method for Markov information source, where a symbol sequence is mapped between 0.0 and 1.0 on the number line, and its coordinate is encoded into a codeword indicated by, for example, binary notation.
FIG. 1 is a conceptual drawing of the above method. For simplifying an explanation, binary symbols xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d are supplied at random out of a memoryless state, which is independent of past occurrence states. In this case, an occurrence probability of symbol xe2x80x9c1xe2x80x9d is defined as r and an occurrence probability of symbol xe2x80x9c0xe2x80x9d is expressed as 1xe2x88x92r. A range for the symbol xe2x80x9c1xe2x80x9d is placed at the bottom of the figure. The length of an output sequence of memoryless source is assumed to be three, and coordinates for C(000) through C(111) shown in the right rows are respectively expressed by binary numbers. These binary numbers are cut off at digit, where the number can be identified, and the binary numbers are defined as respective codewords. By defining as above, the codewords can be decoded at a receiving side by operating a process similar to a transmitting side.
In the above case, a mapping range Ai for mapping on the number line of the symbol sequence at the i-th point, minimum coordinates Ci of the mapping range Ai are as follows where an initial value of the mapping range is A0=1.0 and the minimum coordinates C0=0.0:
when an occurring symbol value ai is xe2x80x9c0xe2x80x9d,
Ai=(1xe2x88x92r)Aixe2x88x921
Ci=Cixe2x88x921+rAixe2x88x921;
and
when the symbol value ai is xe2x80x9c1xe2x80x9d,
Ai=rAixe2x88x921
Ci=Cixe2x88x921
As described in xe2x80x9cAn overview of the basic principles of the Q-coder Adaptive binary arithmetic coderxe2x80x9d (IBM Journal of Research and Development Vol. 32 No. 6, November, 1988), in order to reduce a number of operations such as a multiplication with large operational load, instead of calculating rAixe2x88x921, a set of fixed values S may be provided as a table. Encoding and decoding with finite precision is implemented by selecting a value corresponding to Markov status out of the table.
Accordingly, as mapping is continuously repeated, the range (interval) Aixe2x88x921 becomes smaller, renormalization is performed (e.g., Aixe2x88x921 is multiplied by power of 2 to keep the value Aixe2x88x921 more than a predefined value), and an operational precision is kept under a virtual decimal point by virtually resetting a decimal point. In obtaining an actual codeword, the above set of fixed values can be always used.
Here, by approximating rAixe2x88x921 to S, each of the above expressions becomes each of the following:
when the symbol value ai is xe2x80x9c0xe2x80x9d,
Ai=Aixe2x88x921xe2x88x92S
Ci=Cixe2x88x921+S;
and
when the symbol value ai is xe2x80x9c1xe2x80x9d,
Ai=S
Ci=Cixe2x88x921
The range (interval) Aixe2x88x921 resulted from the previous symbol, essentially becomes smaller as mapping is continuously repeated, thus, S should accordingly be reduced. This reduction can be performed by shifting operation into one n-th (n is power of 2). However, the reduction of S causes to increase a number of 0 aligning in the high order bits of S, which does not directly effect to the operation. On the contrary to the above operation, by multiplying Aixe2x88x921 by power of 2 and by keeping Aixe2x88x921 more than a minimum value (1/2), it is possible that S having the fixed value is used. The foregoing process is called renormalization.
In the following explanation, a symbol is called MPS (more probable symbol: symbol having higher probability of occurrence) when the symbol ai is xe2x80x9c0xe2x80x9d, and a symbol is called LPS (less probable symbol: symbol having lower probability of occurrence) when the symbol ai is xe2x80x9c1xe2x80x9d. Namely, a prediction conversion is previously performed and MPS showing a higher probability of occurrence or LPS showing a lower probability of occurrence is assigned to each symbol. And when the symbol ai is xe2x80x9c1xe2x80x9d, the range
Ai=rAixe2x88x921=S
becomes a range (interval) of the less probable symbol.
FIG. 2 is a block diagram showing an example of an encoder of a conventional encoding apparatus. In the figure, reference numeral 1 shows a register for temporarily storing a value of range (interval) assigned to the previous symbol. Reference numeral 2 shows a subtracter, 3 shows a switch of range (interval), 4 shows a switch of coordinates, 5 shows a shifter for determining a shifting amount for renormalization, and 6 shows a calculator for calculating encoded output.
Next, an operation of the apparatus will be described referring to the figure.
S (within a range (interval) of LPS), which is previously selected from the states of Markov information source based on the table specifying a plurality of values at a prediction estimator (not shown in the figure), is entered to the subtracter 2. The subtracter 2 obtains and outputs a difference (Aixe2x88x921xe2x88x92S) from the range (interval) Aixe2x88x921 for the previous symbol stored in the register 1.
The switch 3 receives the range (interval) (Aixe2x88x921xe2x88x92S) assigned to MPS and the range (interval) S assigned to LPS, and the switch 3 switches the range according to whether the symbol is MPS or LPS. Namely, when the symbol is MPS, the range (interval) Ai assigned to the symbol is determined and output as
Ai=Aixe2x88x921xe2x88x92S
and when the symbol is LPS, the range (interval) Ai assigned to the symbol is determined and output as
Ai=S
The switch 4 selects one of the range (interval) S for LPS and a fixed value 0 according to whether received symbol is MPS or LPS and outputs the selected value as xcex94C, difference coordinates between the range (interval) assigned to the previous symbol and the minimum coordinates Cixe2x88x921. Namely, when the received symbol is MPS placed in the high order bit, the difference coordinates xcex94C is output as
xcex94C=S
when the received symbol is LPS placed in the low order bit, the difference coordinates xcex94C is output as
xcex94C=0
The output Ai of the switch 3 is supplied to the register 1 and to the shifter 5.
The range (interval) Ai assigned to the symbol ai is stored in the register 1 and the range (interval) for a next symbol is calculated based on the data of Ai. The shifter 5 compares the range (interval) Ai with {fraction (1/2+L )}. When the range (interval) Ai is smaller than {fraction (1/2+L )}, the shifter 5 doubles the range (interval) Ai and compares the doubled result of the range (interval) Ai with {fraction (1/2+L )} again. The shifter 5 repeats this doubling of the range (interval) Ai until the doubled result of the range (interval) Ai is greater than {fraction (1/2+L )}. The number 1 of the above doublings is obtained and output to the register 1 and the calculator 6 as a shifting amount 1. Then, the calculator 6 calculates a codeword using the outputs supplied from the switch 4 and the shifter 5 and outputs the codeword. The calculator 6 stores difference coordinates accumulated from the past. Namely, this accumulated value equals to the minimum coordinates Cixe2x88x921 of the range (interval) assigned to the previous symbol. The input difference coordinates xcex94C is added to the minimum coordinates Cixe2x88x921 of the previous symbol to obtain the minimum coordinates Ci of the range (interval) assigned to the present symbol. The minimum coordinates Ci is shifted by the shifting amount 1 (bits). Then, it is checked whether one of the high order bits of the maximum coordinates within the effective range matches to any of the high order bits of the shifted minimum coordinates Ci. If there exists a bit matched, the matched bit is determined and output as determined bit of coordinates, in other words, a codeword.
Next, the general arithmetic encoder and the general arithmetic decoder will be explained in detail.
The encoder and decoder using arithmetic encoding and decoding can be embodied using the table and the processing flow described in the International Standard Recommendation T.82 of ITU-T (International Telecommunication Union). In the following explanation, the arithmetic encoder is referred to as a QM-Coder, the encoder is as a QM encoding section 7, and the decoder is as a QM decoding section 8. FIGS. 3 and 4 show general configurations of the encoder and the decoder. On the contrary to FIG. 1, in the QM-Coder, the range for LPS (symbol xe2x80x9c1xe2x80x9d) on the number line is placed in the upper part of the figure.
In FIG. 3, a reference numeral 9 shows an image memory for storing an input image and a reference numeral 10 shows a prediction value table (MPS table) storing a pixel value MPS (More Probable Symbol), which has a high probability of occurrence, as a prediction value of one bit. A reference numeral 11 shows a state table (ST table) storing a state number (0-112) of 7 bits. This state number is for classifying the state of matching probability of the prediction value into a total of 113 states. A reference numeral 12 shows an LPS interval size table (LSZ table) specifying a size of an LPS interval by 16 bits. 13 denotes a next MPS state table (NMPS table) specifying a next state for MPS transition by 7 bits. 14 denotes a next LPS state table (NLPS table) specifying a next state for LPS transition by 7 bits. 15 denotes a prediction switching table (SWTCH table) showing inversion of the prediction value of the MPS table 10 by one bit. 16 denotes a pixel-to-symbol converter inputting a prediction value of the MPS table 10 and a pixel PIX supplied from the image memory 9 and outputting a symbol. 17 and 18 denote update processors updating the values of the MPS table 10 and the ST table 11. 19 denotes an arithmetic encoder.
In this case, the above MPS table 10 and the ST table 11 are variable tables. The above LSZ table 12, the NMPS table 13, the NLPS table 14, and the SWTCH table 15 are constant tables (probability estimation tables). In the following, an operation of the encoding apparatus will be explained referring to FIG. 3.
In FIG. 3, a QM encoding section 7 receives two inputs, one of which is a context and the other is an encoding pixel. The QM encoding section 7 outputs a code.
The image memory 9 stores an image and generates a context (10 bits, a total of 1024 patterns=210), which is a reference pattern of 10 adjacent pixels, already encoded or decoded, indicated by Model Template for an encoding pixel. The image memory 9 also outputs the encoding pixel at the time of encoding. The QM-Coder is provided with 2-line and 3-line standard model templates for generating a context as shown in FIG. 5.
In the QM-Coder, a prediction matching probability of pixel value is estimated for each context of each encoding pixel, and encoding is performed by learning the change of the prediction matching probability of pixel value. Learning is implemented by rewriting values of two variable tables having indexes of contexts as shown in FIGS. 40 and 41 (namely, the MPS table 10 indicating a prediction value by one bit corresponding to the context, and the ST table 11 indicating a state by seven bits corresponding to the context).
The QM-Coder includes a constant table (probability estimation table) for referring state number (state) on encoding as an index as well as the variable tables. FIG. 42 shows values set in the constant table. A prefix such as xe2x80x9c0xxe2x80x9d of xe2x80x9c0x08000xe2x80x9d indicates hexadecimal number. In FIG. 42, the LSZ table 12 shows a size of LPS interval by LSZ value of 16 bits, the NMPS table 13 shows a next state for MPS transition by NMPS value of seven bits, the NLPS table 14 shows a next state for LPS transition by NLPS value of seven bits, and an SWTCH table 15 shows an inversion of prediction value by SWTCH value of one bit. (These names expressed by capital alphabet letters for variable and constant tables will be used as array names in processing flow explained below.)
The size of LPS interval of the LSZ table 12 is referred to by a calculator, which is not shown in the figure, of the arithmetic encoder 19 and is not directly related to learning of adaptive prediction. In the arithmetic encoder 19, a calculation is operated using the LSZ, and when an operation precision is reduced, the operation is renormalized. When the renormalization occurs, learning is performed at the same time.
If the encoding symbol is MPS when renormalization occurs, the NMPS value of the NMPS table 13 is written in the ST table 11. If the encoding symbol is LPS, the NLPS value of the NLPS table 14 is written in the ST table 11 (this operation means the state corresponding to the context is rewritten). The state is thus moved. On encoding, the pixel-to-symbol converter 16 outputs the symbol to the arithmetic encoder 19 and the update processors 17 and 18.
If the renormalization is due to the LPS, and when the prediction matching probability is less than around {fraction (1/2+L )}, the MPS value is inverted (operation xe2x80x9c1-MPSxe2x80x9d) and the inverted value is written in the MPS table 10. Whether the prediction matching probability is less than {fraction (1/2+L )} or not can be determined by the SWTCH value of the SWTCH table 15 as a flag.
Namely, the SWTCH value of the SWTCH table 15 is set to xe2x80x9c1xe2x80x9d for the state where the prediction matching probability is less than around {fraction (1/2+L )} and the SWTCH value of the SWTCH table 15 other than the above case is set to xe2x80x9c0xe2x80x9d. By setting like above, the SWTCH value of the SWTCH table 15 can indicate the prediction value as an inversion flag.
As has been described, the ST table 11 and the MPS table 10 should be updated and controlled, respectively. As shown in FIG. 3, the update processors 17 and 18 determine the updating values for the ST table 11 and the MPS table 10, respectively. The update processors 17 and 18 also respectively rewrite the values of the tables with the above values. The updating process has been thus performed.
FIG. 6 shows a state transition diagram in the QM-Coder operated based on the table shown in FIG. 42 (since the number of the states is too large as 113 to show in the figure, only a part of the state transition is described). Each block shows one state and has a state number (a parenthesized number is hexadecimal notation) inside of the block. An arrow with xe2x80x9cMPSxe2x80x9d shows a state transition due to MPS (and accompanied with renormalization). An arrow with xe2x80x9cLPSxe2x80x9d shows a state transition due to LPS. Next states for the state transitions due to MPS and LPS are shown in the NMPS table 13 and the NLPS table 14, respectively. LPS state transition shown by underlined LPS means LPS state transition accompanied by inversion of the prediction value, which is indicated in the SWTCH table 15 as the SWTCH value xe2x80x9c1xe2x80x9d.
An example of the state transition will be explained. On starting the encoding process, values are initialized for all contexts as xe2x80x9cstate=0, prediction value=0xe2x80x9d, as shown in FIGS. 43 and 44. To simplify the explanation, it is assumed that context CX for a plurality of sequential pixels continuously takes the same value (e.g., CX=1). A state number and a prediction value for the context CX can be obtained as ST[CX] and as MPS[CX] by referring to the variable table. When LPS occurs as a first symbol, the state ST[CX] is moved to 1 from 0. The next state for the LPS state transition is shown as:
NLPS[ST[CX](=0)]=1
and the value of ST[CX] of the ST table 11 is updated to:
ST[CX]=1
as shown in FIG. 45. At this time, the prediction value is simultaneously updated since:
SWTCH[ST[CX](=0)]=1
(this is also shown in the figure as underlined xe2x80x9cLPSxe2x80x9d). Namely, MPS [CX] of the MPS table 10 becomes 1 (inversion value) from 0 as shown in FIG. 46. When a second symbol occurs as LPS, the next state for the state transition is:
NLPS[ST[CX](=1)]=14
and the value of ST[CX] of the ST table 11 is updated as:
ST[CX]=14
as shown in FIG. 47. At this time, since:
SWTCH[ST[CX](=1)]=0,
the prediction value of the MPS table 10 does not need to be inverted. If a third symbol occurs as MPS, the state is moved to a next state only when the renormalization occurs. For explanation of the operation, it is assumed the state is moved, the next state is:
NMPS[ST[CX](=14)]=15
and the value of ST[CX] of the ST table 11 is updated to:
ST[CX]=15
as shown in FIG. 48.
The state transition explained hereinbefore is indicated by xe2x80x9c***xe2x80x9d in the figure. The state transition will be the same on decoding process.
Before explaining an encoding processing flow, bit assignments of an encoding register 20 and an interval size register 21 included in the arithmetic encoder 19 are shown in FIG. 7.
In the encoding register 20, a decimal point is placed between 15th bit and 16th bit, xe2x80x9cxxe2x80x9d (16 bits) shows a calculation part (Cx22) for the LSZ table 12. If the calculation results in carry-over, the bits of xe2x80x9cxxe2x80x9d is propagated to the high order bit. xe2x80x9csxe2x80x9d (3 bits) shows a spacer bit part (Cs23), xe2x80x9cbxe2x80x9d (8 bits) shows a bite output part (Cb24), and xe2x80x9ccxe2x80x9d (1 bit) shows a carry detector (Cc25). In the encoding process, the value of the encoding register 20 is updated to the lower bound of the range corresponding to the encoded symbol.
In the interval size register 21, a decimal point corresponds to the decimal point of the encoding register 20, and decimals xe2x80x9caxe2x80x9d (16 bits) are placed corresponding to register part xe2x80x9cxxe2x80x9d. Only for the initial value, an integer (16th bit) becomes xe2x80x9c1xe2x80x9d. The interval size (also called as an interval range) is updated to A-LSZ (lower sub-interval size) or LSZ (upper sub-interval size). Except for the initial value (integer part=xe2x80x9c1xe2x80x9d), 15th bit showing the weigh of {fraction (1/2+L )} is renormalized to xe2x80x9c1xe2x80x9d. By keeping the value of the interval size register 21 over {fraction (1/2+L )}, it is guaranteed the lower sub-interval can be obtained for any LSZ values selected from the LSZ table 12 as the upper sub-interval size. In renormalization, both of the interval size register 21 and the encoding register 20 are extended (shifted) simultaneously.
In the QM-Coder, xe2x80x9cconditional MPS/LPS exchangexe2x80x9d is performed, namely, the upper sub-interval LSZ, having a fixed size corresponding to the state and selected from the LSZ table 12, is usually assigned to LPS and is assigned to MPS when the lower sub-interval is less than the upper sub-interval. Renormalization is implemented after encoding LPS or encoding MPS when xe2x80x9cconditional MPS/LPS exchangexe2x80x9d is applied.
In the following, processing flow of the encoding is explained by referring to the bit assignment of the register. In the processing flow, xe2x80x9clayerxe2x80x9d means xe2x80x9clayer (of the resolution)xe2x80x9d in case of hierarchical encoding and xe2x80x9cstripexe2x80x9d means xe2x80x9cstripexe2x80x9d of the image divided by N line unit (only the last stripe may have lines equal to or less than N lines). Here, the number of layers is assumed to be 1, however, this encoding process can be applied to a plurality of layers.
The following auxiliary variables CT 26, BUFFER 27, SC 28 and TEMP 29 are used for explaining the encoding process as well as variables, tables, and registers described above in the explanation of FIGS. 3, 7 and 42. The auxiliary variable CT 26 counts the number of shifts by the renormalization implemented in the encoding register 20 and the interval size register 21. When the value becomes 0, the CT 26 outputs a next encoding bite. The auxiliary variable BUFFER 27 stores the encoding bite value supplied from the encoding register 20. The auxiliary variable SC 28 is used only for encoding. The SC 28 counts the number of 0xff continuously occur when the encoding register 20 outputs the encoding bite value 0xff. The auxiliary variable TEMP 29 is used only for encoding. The TEMP 29 detects the carry to the BUFFER 27, obtains the low order 8 bits of the carry-over number as a new value of the BUFFER 27. The BUFFER 27 is set by the encoding register 20 through the TEMP 29. The BUFFER 27 never becomes 0xff without carry-over. In case of carry-over to the high order bits, the bits, the order of which is lower than the BUFFER 27, namely, the BUFFER 27 and SC number of 0xff, are changed. Accordingly, the code output from the encoding register 20 cannot be determined.
FIG. 8 is a flowchart showing a general encoding process of the ENCODER. In this processing flow of the Recommendation T. 82, prediction process for TP (Typical Prediction) and DP (Deterministic Prediction) is shown. Process for TP and DP is not directly related to the present invention nor the conventional art, thus an explanation for TP and DP is omitted. First, at step S101, INITENC is called to perform initialization of encoding process. At step S102, a pair of the pixel PIX and the context CX is read one by one to be encoded by the encoder (ENCODE) at step S103. At step S104, S102 and S103 are repeated until the stripe (or the image) is finished to be supplied. When the stripe is finished to be supplied, FLUSH is called to perform termination process at step S105.
FIG. 9 is a flowchart showing ENCODE processing flow. In this flow, a process to be called is switched based on match or mismatch between the encoding pixel value (PIX) and the output value (prediction value) of the MPS table 10. At step S111, match or mismatch between the pixel value and the prediction value is detected. When match is detected, the encoder encodes MPS, and when mismatch is detected, the encoder encodes LPS. At step S113, CODEMPS is called to encode MPS, and at step S112, CODELPS is called to encode LPS.
FIG. 10 is a flowchart showing CODELPS processing flow. The CODELPS is called for encoding LPS, namely, the mismatch is detected between the encoding pixel value (PIX) and the output value (prediction value) of the MPS table 10. At step S121, the value of the interval size register 21 is temporarily updated to the lower sub-interval size. At step S122, it is checked whether the LPS interval is greater than the MPS interval. If step S122 results in xe2x80x9cYesxe2x80x9d, conditional MPS/LPS exchange is applied. Namely, the value of the interval size register 21 is unchanged to encode the lower sub-interval and the encoding register 20A is not updated. If step S122 results in xe2x80x9cNoxe2x80x9d, the upper sub-interval is encoded. That is, at step S123, the encoding register 20 is updated as the lower bound and at step S 124, the interval size register 21 is updated as the interval size. When the constant SWTCH value of the SWTCH table 15 equals xe2x80x9c1xe2x80x9d at step S125, the prediction value (MPS table 10) is inverted or updated at step S126. In LPS encoding, the state transition referring to the NLPS table 14 is performed at step S127. At step S128, renormalization is implemented by calling RENORME.
FIG. 11 is a flowchart showing CODEMPS processing flow. The CODEMPS is called for encoding MPS, that is, the encoding pixel (PIX) matches to the output value (prediction value) of the MPS table 10. First, at step S131, the value of the interval size register 21 is temporarily updated to the lower sub-interval size. At step S132, it is detected whether the renormalization is required or not by checking the interval range is smaller than xe2x80x9c0x8000xe2x80x9d showing a minimum value of the interval size (weigh of {fraction (1/2+L )}). If step S132 results in xe2x80x9cNoxe2x80x9d, CODEMPS process is finished. If step S132 results in xe2x80x9cYesxe2x80x9d, the state transition is implemented referring to the NMPS table 13 at step S136. And at step S137, the renormalization is implemented by calling RENORME. Before steps S136 and 137, if step S133 results in xe2x80x9cYesxe2x80x9d, the interval size register 21 does not change for encoding the lower sub-interval and the encoding register 20 is not updated. If step S133 results in xe2x80x9cNoxe2x80x9d, conditional MPS/LPS exchange is applied. At step S134, the encoding register 20 is updated and the interval size register 21 is updated at step S135.
FIG. 12 shows RENORME processing flow for implementing the renormalization. In the figure, xe2x80x9c less than  less than 1xe2x80x9d shows an operation to shift the value of the register to higher order by 1 bit. To shift the value of the interval size register 21 and the encoding register 20 to higher order by 1 bit at steps S141 and S142 means to perform an operation equal to the multiplication by 2. At step S143, 1 is subtracted from the variable CT 26 and at step S144, it is checked whether the variable CT 26 is 0 or not. If step S144 results in xe2x80x9cYesxe2x80x9d, BYTEOUT process is called at step S145 and the encoding register 20 outputs 1 byte code. At step S146, completion of the renormalization is detected. If the value of the interval size register 21 is less than 0x8000, steps S141 through S145 are repeated. If the value of the interval size register 21 is equal to or more than 0x8000, the interval becomes more than {fraction (1/2+L )} and the renormalization process is completed.
FIG. 13 shows BYTEOUT processing flow for outputting codes one by one from the encoding register 20. In the figure, xe2x80x9c greater than  greater than 19xe2x80x9d means an operation to shift the value of the register to lower order by 19 bits. The byte output section (Cb 24) of the encoding register 20 is to be output. The carry detector (Cc 25) operates at the same time for detecting carry-over. At step S151, 9 bits of the sum of the value (Cb 24) and the value (Cc 25) of the encoding register are set to the variable TEMP 29. If the carry-over has occurred at step S152: TEMP greater than 0x100; Cc=1.
If the carry-over has not occurred, it is checked whether TEMP=0xff or TEMP less than 0xff at step S159. The byte output is processed by two ways based on the check at step S159. If step S152 results in xe2x80x9cYesxe2x80x9d, at step S153, the code already output from the encoding register 20 and stored as the BUFFER 27 and carry value 1 is written. At step S154, SC number of byte value 0 (stacked 0xff has been converted to 0x00 by the carry) is written and xe2x80x9cSC+1xe2x80x9d bytes of the code value with carry-over is determined. At step S155, the variable SC 28 is set to 0 and at step S156, the low order 8 bits of the variable TEMP are set to the variable BUFFER 27. In the figure, xe2x80x9candxe2x80x9d shows AND operation. At step S157, (Cc 25) and (Cb 24) of the encoding register 20, which are processed as variable TEMP 29, are cleared. At step S158, 8 is set to the variable CT 26 for processing 8 bits until next byte output. If step S159 results in xe2x80x9cYesxe2x80x9d, the code is not determined and the variable SC 28 is incremented to accumulate 0xff. If step S159 results in xe2x80x9cNoxe2x80x9d, the code already output from the encoding register 20 is written as the BUFFER 27 at step S161. At step S162, SC number of byte value 0x00 are written and the code value of xe2x80x9cSC+1xe2x80x9d bytes is determined. At step S163, 0 is set to the variable SC 28 and at step S164, the variable TEMP 29 (8 bits, without carry-over) is set to the variable BUFFER 27.
FIG. 14 shows INITENC processing flow for setting the initial values of the ST table 11, the MPS table 10 and each variable at starting time of the encoding. In the figure, at step S171, xe2x80x9cthe first stripe of this layerxe2x80x9d means xe2x80x9cimagexe2x80x9d itself when an image encoding does not include a concept of layer or stripe. At starting time of encoding an image, INITENC is implemented. In case of an image consisting of a plurality of stripes, processing can be continued without initializing the variable tables for each stripe. At step S171, it is checked if this is the first stripe of the pixel of this layer or forced reset of the tables. If step S171 results in xe2x80x9cYesxe2x80x9d, the ST table 11 and the MPS table 10, which are the variable tables for all the contexts CX 2, are initialized at step S172. The SC 28, the interval size register 21, the encoding register 20 and the variable CT 26 are initialized at steps S173, S174, S175 and S176, respectively. The initial value of the CT 26 is the sum of the number of bits of (Cb24) and bits of (Cs23) of the encoding register 20. After processing 11 bits, the first code is output. If step S171 results in xe2x80x9cNoxe2x80x9d, the table values at the end of the previous stripe of this layer are set to the variable tables at step S177 instead of the initialization.
FIG. 15 shows FLUSH processing flow for implementing termination process including sweeping out the remaining value in the encoding register 20. At step S181, CLEARBITS is called to minimize the number of effective bits of the code remaining in the encoding register 20. At step S182, FINALWRITES is called to finally output the variable BUFFER 27, SC 28 and the code of the encoding register 20. At step S183, the first byte of the code is removed because the variable BUFFER 27 is output (as integer part of the code) prior to the value output from the encoding register 20. At step S184, the byte xe2x80x9c0x00xe2x80x9d at the end of the code can be removed, if desired, because the code is decimal coordinates within the final effective range.
FIG. 16 shows CLEARBITS processing flow for minimizing the number of effective bits of the code at the end of encoding. By this process, the code is determined to be the value that ends with the greatest possible number of xe2x80x9c0x00xe2x80x9d. At step S191, the variable TEMP 29 is set to the value obtained by clearing the low-order byte (Cx 22) of the upper bound value of the final effective range of the encoding register 20. At step S192, it is checked if the value obtained by clearing the low-order two bytes of the upper bound value is larger than the value of the encoding register 20. If step S192 results in xe2x80x9cYesxe2x80x9d, overcleared byte is returned to the variable TEMP 29 at step S193 and the value of the encoding register 20 is set to the remaining value after returning the overcleared byte. If step S192 results in xe2x80x9cNoxe2x80x9d, the value of the variable TEMP 29 is set in the encoding register 20.
FIG. 17 shows FINALWRITES processing flow for writing the code determined at the end of encoding including remaining value in the encoding register 20. At step S201, encoding register 20 is shifted by the number of bits shown by the variable CT 26 to enable to output the code and to detect the carry. At step S202, it is checked if the carry has occurred or not. If step S202 results in xe2x80x9cYesxe2x80x9d, the carry has occurred and if xe2x80x9cNoxe2x80x9d, the carry has not occurred. As well as in the BYTEOUT processing flow, the code of xe2x80x9cSC+1xe2x80x9d bytes is determined by writing the code value already output from the encoding register 20 at steps S203 and S204 for the code value with the carry or at steps S207 and S208 for the code value without the carry. At step S205, the value of (Cb 24) (1 byte) of the encoding register is output. At step S206, the code is finished to be output by outputting the low-order 1 byte of the value of (Cb 24).
Next, a decoding apparatus and decoding method of the apparatus will be explained.
In FIG. 4, a reference numeral 9 shows an image memory for storing an input image. A reference numeral 10 shows an MPS table for storing MPS (More Probable Symbol) of 1 bit, which is a pixel value having high probability of occurrence, as a prediction value. A reference numeral 11 shows an ST table for storing state number (0-112) of 7 bits. This state number is for classifying the state (State) of matching probability of the prediction value into a sum of 113. A reference numeral 12 shows an LSZ table specifying a size of an LPS interval by 16 bits. 13 shows an NMPS table specifying a next state for the MPS transition by 7bits. 14 shows an NLPS table specifying a next state of the LPS transition by 7 bits. 15 shows an SWTCH table indicating an inversion of the prediction value by 1 bit. 61 shows a symbol-to-pixel converter inputting a prediction value of the MPS table 10 and a pixel PIX supplied from the image memory 9 and outputting symbols. 17 and 18 respectively show update processors for updating the values of the MPS table 10 and the ST table 11. A reference numeral 30 shows an arithmetic decoder.
Similar to the encoding apparatus, the MPS table 10 and the ST table 11 are variable tables. The LSZ table 12, the NMPS table 13, the NLPS table 14 and the SWTCH table 15 are constant tables (probability estimation tables). The value identical to each table shown in FIG. 3 should be set in each of the above tables. An operation of the decoding apparatus will be described in the following referring to FIG. 4.
In FIG. 4, a QM decoding section 8 receives two inputs, one of which is a context and the other is a code. The QM decoding section 8 outputs a decoded pixel.
The image memory 9 accumulates images and generates a context (10 bits, the sum of 1024), which is reference pattern of 10 adjacent encoded/decoded pixels indicated by the model template for decoding pixel. In the QM-Coder, 2-line and 3-line standard model templates are provided and commonly used for encoding/decoding.
In the QM-Coder, the matching probability of the prediction value of the pixel of each context for decoding pixel is estimated to proceed decoding with learning accompanied with the variation of the matching probability as well as the encoding apparatus. Learning is performed by rewriting two variable tables (the MPS table 10 and the ST table 11), an index of which is a context. Other than the variable tables, the QM decoding section 8 includes constant tables (probability estimation tables) for referring to the state number (state) as index on decoding. The values shown in FIG. 42 are set in these constant tables. The constant tables are the LSZ table 12 specifying the LPS interval size by 16 bits, the NMPS table 13 specifying a next state for the MPS state transition by 7 bits, the NLPS table 14 specifying a next state for the LPS state transition by 7 bits and the SWTCH table 15 specifying the inversion of the prediction value by 1 bit. (These English names for the variable and constant tables will be used for names of arrays in the processing flow explained below.)
The LPS interval size of the LSZ table 12 is referred to by a calculator, which is not shown in the figure, inside of the arithmetic decoder 30. The LPS interval size is not directly related to learning of adaptive prediction. In the arithmetic decoder 30, the calculator operates using the LSZ and implements renormalization when an operation precision is reduced. When the renormalization occurs, learning is performed at the same time.
If the decoding symbol is MPS when the renormalization is implemented, the NMPS value of the NMPS table 13 is written in the ST table 11. If the decoding symbol is LPS when the renormalization is implemented, the NLPS value of the NLPS table 14 is written in the ST table 11. The state is moved to a next state. On decoding, the arithmetic decoder 30 outputs a symbol to the symbol-to-pixel converter 61 and the update processors 17 and 18.
When the renormalization due to the LPS is implemented, if the prediction matching probability is less than around 1/2, the MPS value is inverted (operation xe2x80x9c1-MPSxe2x80x9d) and the inverted value is written in the MPS table 10. Whether the matching probability is less than around 1/2 or not can be detected by the SWTCH value of the SWTCH table 15 as a flag.
As has been described, the ST table 11 and the MPS table 10 should be respectively updated and controlled. In FIG. 4, the update processors 17 and 18 determine the updating values and rewrite the values of the ST table 11 and the MPS table 10, respectively.
Before explaining the decoding processing flow, as the same with the encoding, bit arrays of the decoding register 31 and the interval size register 32, provided inside of the arithmetic decoder 30, will be shown in FIG. 19.
In the decoding register, a low-order word CLOW 33 and a high-order word CHIGH 35 can be embodied by the registers of 32 bits. A decimal is set at position upper to the bit 31, which is MSB (Most Significant Bit). xe2x80x9cbxe2x80x9d (8 bits) is a high-order byte Cb 34 of the byte inputting part (CLOW register 33), and xe2x80x9cxxe2x80x9d (16 bits) is calculating part Cx 36 (CHIGH register 35) corresponding to the value of the LSZ table 12. In the decoding process, the value of the C register is updated to an offset value of the code, which is coordinate of the interval, from the lower bound value of the interval corresponding to the decoded symbol.
In the interval size register 32, a decimal is set corresponding to the decimal of the decoding register 31, and xe2x80x9caxe2x80x9d (16 bits) is placed as decimal part corresponding to the register part xe2x80x9cxxe2x80x9d. At initial state, the integer part (bit 16) of the interval size register 32 becomes xe2x80x9c1xe2x80x9d. The interval size (also called xe2x80x9cinterval sizexe2x80x9d) is updated to xe2x80x9cA-LSZxe2x80x9d (lower sub-interval size) or LSZ (upper sub-interval size). The interval size register 32 is renormalized so that bit 15 showing weigh of {fraction (1/2+L )} becomes xe2x80x9c1xe2x80x9d except the initial value (the integer part=xe2x80x9c1xe2x80x9d). It is guaranteed that the lower sub-interval is obtained even if any LSZ is selected from the LSZ table 12 as the upper sub-interval size by keeping the weigh more than {fraction (1/2+L )}. In the renormalization, the interval size register 32 and the decoding register 31 are extended (shifted) simultaneously.
In the OM-Coder, the upper sub-interval LSZ given by the LSZ table 12, which is fixed size for any state, is usually assigned to LPS. When the lower sub-interval becomes smaller than the upper sub-interval, the upper sub-interval LSZ is assigned to MPS by xe2x80x9cconditional MPS/LPS exchangexe2x80x9d. In decoding LPS, or decoding MPS by applying xe2x80x9cconditional MPS/LPS exchangexe2x80x9d, renormalization is implemented.
The decoding processing flow will be explained according to the bit array of the register. In the processing flow, a term xe2x80x9clayerxe2x80x9d is interpreted in the same way as the encoding process, and the decoding process is explained assuming the number of layers=1. This decoding process can be applied to a plurality of layers.
For explaining the decoding processing flow, the following auxiliary variables CT 26 and BUFFER 27 are used other than the variables, tables and registers shown in FIGS. 4, 19 and 42. The CT 26 is the auxiliary variable for counting the number of shifts of the decoding register 31 and the interval size register 32 in the renormalization, and inputting the next code byte when the number of shifts becomes 0. The BUFFER 27 is the auxiliary variable for storing code byte value to be input to the Cb register 34 of the decoding register 31 from the code.
FIG. 18 shows DECODER processing flow illustrating a whole decoding process. In this processing flow of the Recommendation T. 82, process for TP (Typical Prediction) and DP (Deterministic Prediction) is shown. Process for TP and DP is not directly related to the present invention nor the conventional art, thus an explanation for TP and DP is omitted. First, at step S211, INITDEC is called to initialize the decoding process. At step S212, a set of the contexts CX 2 is read one by one. At step S213, the pixel PIX is decoded by the process DECODE. At step S214, steps S212 and S213 will be repeated until the stripe (or the image) is finished to be supplied.
FIG. 20 shows DECODE processing flow for decoding the decoding pixel. First, at step S221, the interval size register 32 is temporarily updated to the lower sub-interval size. If step S222 results in xe2x80x9cYesxe2x80x9d, the lower sub-interval is decoded. If step S223 results in xe2x80x9cYesxe2x80x9d, MPS_EXCHANGE is called at step S224 and RENORMD is called at step S225 to implement the renormalization. If step S223 results in xe2x80x9cNoxe2x80x9d, the MPS is decoded without implementing the renormalization, and the prediction value of the MPS table 10 is determined as the pixel value (PIX). If step S222 results in xe2x80x9cNoxe2x80x9d, the upper sub-interval is decoded. LPS_EXCHANGE is called at step S227 and RENORMD is called at step S228 to implement the renormalization. In the path for calling MPS_EXCHANGE and LPS_EXCHANGE, even if the decoding interval is determined, it is impossible to know which should be decoded between MPS and LPS without detecting which is larger, MPS or LPS. Accordingly, each pixel value is determined by the called processing flow.
FIG. 21 shows LPS_EXCHANGE processing flow for decoding the upper sub-interval. If step S231 results in xe2x80x9cYesxe2x80x9d, the MPS is decoded. At step S232, the decoding register 31 is updated and the interval size register 32 is updated at step S233. At step S234, the prediction value obtained from the MPS table 10 is determined as the pixel value (PIX) without any change. At step S235, a state is moved to a next state by referring to the NMPS table 13. If step S231 results in xe2x80x9cNoxe2x80x9d, the LPS is decoded. At step S236, the decoding register 31 is updated and the interval size register 32 is updated at step S237. At step S238, non-prediction value xe2x80x9c1-prediction valuexe2x80x9d is determined as the pixel value (PIX). If step S239 results in xe2x80x9cYesxe2x80x9d, the prediction value (MPS table 10) is inverted or updated at step S240. At step S241, a state is moved to a next state by referring to the NLPS table 14.
FIG. 22 shows MPS_EXCHANGE processing flow for decoding the lower sub-interval. If step S251 results in xe2x80x9cYesxe2x80x9d, the LPS is decoded. At step S252, non-prediction value is determined as the pixel value (PIX). If step S253 results in xe2x80x9cYesxe2x80x9d, the prediction value (MPS table 10) is inverted or updated at step S254. At step S255, a state is moved to a next state by referring to the NLPS table. If step S251 results in xe2x80x9cNoxe2x80x9d, the LPS is decoded. At step S256, the prediction value obtained from the MPS table 10 is determined as the pixel value (PIX) without any change. At step S257, a state is moved to a next state by referring to the NMPS table 13.
FIG. 23 shows RENORMD processing flow for implementing renormalization. At step Ss261, it is checked whether the variable CT 26 is 0 or not. If step S261 results in xe2x80x9cYesxe2x80x9d, BYTEIN is called so as to input 1 byte code into the decoding register 31 at step S262. At step S263, the interval size register 32 is shifted to high-order bit by 1 bit and the decoding register 31 is shifted to high-order bit by 1 bit at step S264. This shifting operation equals to duplication. At step S265, 1 is subtracted from the CT 26. At step S266, it is checked whether the renormalization is completed, that is, the value of the interval size register 32 is less than 0x8000, or not. If the value of the interval size register 32 is less than 0x8000, steps S261 through S265 are repeated. At step S267, it is checked whether the variable CT 26 is 0 or not. If step S267 results in xe2x80x9cYesxe2x80x9d, BYTEIN is called so as to input 1 byte code into the decoding register 31.
FIG. 24 shows BYTEIN processing flow for reading a code into the decoding register 31 byte by byte. In the figure, xe2x80x9cSCDxe2x80x9d (Stripe Coded Data) is a code for stripe. If step S271 results in xe2x80x9cYesxe2x80x9d, no code is to be read at step S272, and the variable BUFFER 27 becomes 0 . At step S273, the variable BUFFER 27 is read into the CLOW register 33 (Cb 34), and at step S274, the variable CT 26 is set to 8 for processing the code of 8 bits until next code is input. If step S271 results in xe2x80x9cNoxe2x80x9d, 1 byte code is read into the variable BUFFER 27 at step S275.
FIG. 25 shows INITDEC processing flow for setting initial values of the ST table 11, the MPS table 10 and each variable at starting time of the decoding. Initialization of the table values of steps S281, S282 and S290 are the same as ones of steps S171, S172 and S177 of INITENC processing flow in the encoding process. The initial value of the decoding register 31 is set by inserting 3 bytes of the code into the Cx register 36 and the Cb register 34. At step S283, the decoding register 31 is cleared, and at step S284, BYTEIN is called so as to insert 1 byte of a code into the Cb register 37. At step S285, the decoding register 31 is shifted by 8 bits, and at step S286, BYTEIN is called so as to insert 1 byte of the code into the Cb register 34. At step S287, the decoding register 31 is shifted by 8 bits, and at step S288, BYTEIN is called so as to insert 1 byte of the code into the Cb register 34. By these steps, the sum of 3 bytes of the code is set to the Cx register 36 and the Cb register 34. The initial value of the interval size register 32 is set at step S289.
According to the encoding method for information source data described in the related art, on encoding the less probable symbol, the state and the prediction value is controlled respectively for each context. For this reason, the state transition and to check whether switching the prediction value is required or not, and to switch the prediction value, if required, are controlled and performed respectively. This causes a problem that a whole number of processes becomes large and implementation of encoding/decoding requires lots of time.
The present invention is provided so as to solve the above-mentioned problem. The invention aims to obtain a high-speed operation of encoding/decoding with less number of processes by making correspondence of the state and the prediction value, controlling and updating the state and the prediction value at once.
According to the present invention, an encoding apparatus includes:
an image memory for storing an image data consisting of pixels, outputting an encoding pixel, and outputting a context configured based on a reference pixel adjacent to the encoding pixel; and
an encoding section for inputting the encoding pixel and the context from the image memory, obtaining a state for the encoding pixel corresponding to the context, determining a prediction value for the encoding pixel from the state, and encoding the encoding pixel based on the prediction value.
The encoding section includes:
a variable table for storing the state corresponding to the context for the encoding pixel as a variable, inputting the context from the image memory, and outputting the state for the encoding pixel;
a constant table for storing an interval size and the prediction value for the state as a constant, inputting the state for the encoding pixel from the variable table, and outputting the interval size and the prediction value for the encoding pixel;
a pixel-to-symbol converter for inputting the encoding pixel from the image memory, inputting the prediction value from the constant table, comparing the encoding pixel with the prediction value, converting the encoding pixel to a symbol, and outputting the symbol; and
an encoder for inputting the interval size for the encoding pixel from the constant table, inputting the symbol from the pixel-to-symbol converter, encoding the symbol based on the interval size, and outputting the symbol encoded.
The variable table includes a state table for storing a combination of the prediction value for the encoding pixel and a value specifying a matching probability between the prediction value and the encoding pixel as a state.
The constant table includes a prediction value table for outputting a prediction value using the state stored in the state table as an index.
The state table stores the state including the prediction value in a predetermined bit, and the predetermined bit of the state table is used as a part of the constant table.
The predetermined bit of the state table is located in either of a high order bit and a low order bit for indicating the prediction value.
The constant table includes a next state table, using the state stored in the state table as an index, for storing a next state for a transition of the state of the state table; and the encoding section includes an update processor for updating the prediction value of the next state by the transition of the state of the state table.
The encoding apparatus is installed in one of a computer, a scanner, a facsimile, a printer, a database, and a semiconductor chip.
According to the present invention, a decoding apparatus includes:
an image memory for storing a received decoded pixel and outputting a reference pixel as a context adjacent to a decoding pixel; and
a decoding section inputting a code, inputting the context from the image memory, obtaining a state for the decoding pixel from the context, determining a prediction value for the decoding pixel from the state, and decoding the decoding pixel from the code based on the prediction value.
The decoding section includes:
a variable table for storing the state, corresponding to the context, for the decoding pixel as a variable, and inputting the context and outputting the state for the decoding pixel;
a constant table for storing an interval size and the prediction value corresponding to the state as a constant, inputting the state for the decoding pixel from the variable table, and outputting one of the interval size for the decoding pixel, the prediction value and a non-prediction value, and;
a decoder for inputting the interval size for the decoding pixel, decoding a code into a symbol, and outputting the symbol; and
a symbol-to-pixel converter for converting the symbol into the decoding pixel by referring to one of the prediction value and the non-prediction value of the constant table and outputting the symbol decoded to the image memory.
The variable table includes a state table for storing a combination of the prediction value for the decoding pixel and a value specifying a matching probability between the prediction value and the decoding pixel as a state.
The constant table includes a prediction value table for outputting the prediction value using the state stored in the state table as an index.
The state table stores the state including the prediction value in a predetermined bit, and the predetermined bit of the state table is used as a part of the constant table.
The predetermined bit of the state table is located in either of a high order bit and a low order bit for indicating the prediction value.
The constant table includes a next state table, using the state stored in the state table as an index, for storing a next state for a transition of the state of the state table; and
the decoding section includes an update processor for updating the prediction value of the next state by the transition of the state of the state table.
The decoding apparatus is installed in one of a computer, a scanner, a facsimile, a printer, a database, and a semiconductor chip.
According to the present invention, an encoding method for generating a context from a plurality of reference pixels adjacent to a pixel for encoding (an encoding pixel), obtaining a prediction value predicting an encoding pixel value based on the context and a state number showing a matching probability of the prediction value, and encoding the encoding pixel based on the prediction value and the state number, the encoding method includes the steps of:
storing a predetermined prediction value corresponding to the state number;
obtaining a state number for the encoding pixel;
determining the prediction value based on the state number;
obtaining a symbol by comparing the prediction value and the encoding pixel;
obtaining an interval based on the state number for the encoding pixel; and
encoding the encoding pixel based on the symbol and the interval.
The encoding method further includes the step of referring indirectly to the prediction value from the state controlled by a state transition.
According to the present invention, a decoding method for generating a context from a plurality of reference pixels adjacent to a pixel for decoding (a decoding pixel), obtaining a prediction value predicting a decoding pixel value based on the context and a state number showing a matching probability of the prediction value, and decoding the decoding pixel based on the prediction value and the state number, the decoding method includes the steps of:
storing a predetermined prediction value corresponding to the state number;
obtaining a state number for the decoding pixel;
determining the prediction value based on the state number;
obtaining an interval based on the state number for the decoding pixel;
inputting a code, decoding the code based on the interval and outputting a symbol; and
obtaining the decoding pixel based on the prediction value and the symbol.
The decoding method further includes the step of referring indirectly to the prediction value from the state controlled by the state transition.
According to the invention, an encoding method for generating a context from a plurality of reference pixels adjacent to a pixel for encoding (an encoding pixel), obtaining a prediction value showing a pixel value having a high probability of occurrence and a state number specifying a matching probability of the prediction value, and encoding the encoding pixel based on the prediction value and the state number, the encoding method comprising the steps of:
extending the prediction value to be constant corresponding to the state number;
determining the prediction value based on the state number by obtaining the state number for the encoding pixel; and
updating the state number for the context according to the change of the probability of occurrence of the pixel; and
the encoding method performs encoding by controlling the state number and the prediction value.
According to the invention, a decoding method for generating a context from a plurality of reference pixels adjacent to a pixel for decoding (a decoding pixel), obtaining a prediction value showing a pixel value having a high probability of occurrence and a state number specifying a matching probability of the prediction value, and decoding the decoding pixel based on the prediction value and the state number, the encoding method includes the steps of:
extending the prediction value to be constant corresponding to the state number;
determining the prediction value based on the state number by obtaining the state number for the decoding pixel; and
updating the state number for the context according to the change of the probability of occurrence of the pixel; and
the decoding method performs decoding by controlling the state number and the prediction value.